// BEGIN CUT HERE
#include <windows.h>
// END CUT HERE
// tag Dynamic Programming, Math, Recursion
//   Single Round Match 249 Round 1 - Division I, Level One 
//   Single Round Match 249 Round 1 - Division II, Level Three
#line 5 "TableSeating.cpp"
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <limits>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

double eps = 1e-8;
class TableSeating {
	public:
	int n;
	map<unsigned int, double> memo; 
	double solve(unsigned int flags, const vector<int>& probs)
	{
		if (memo.find(flags) != memo.end()) return memo[flags];
		double res = 0.0;
		if (flags == 0) return res;
		for (int i = 0; i < probs.size(); ++i)
		{
			double curp = (double)probs[i] / 100.0;
			if (curp < eps) continue;
			unsigned int curflag = (1u << (i + 1)) - 1;
			int availpos = 0; 
			for (int j = 0; j + i <= n; ++j)
			{
				unsigned int curflagpos = curflag << j;
				if ((curflagpos & flags) == curflagpos)
				{
					availpos++;
				}
			}

			for (int j = 0; j + i <= n; ++j)
			{
				unsigned int curflagpos = curflag << j;
				if ((curflagpos & flags) == curflagpos)
				{
					// res += curp * 1.0 / availpos * ((i + 1) + solve(flags - curflagpos, probs));
					res += curp / availpos * ((i + 1) + solve(flags - curflagpos, probs));
				}
			}
		}
		return  memo[flags] = res;
	}

	double getExpected(int numTables, vector <int> probs) {
		memo.clear();
		n = numTables;
		return solve((1u << numTables) - 1, probs);
	}

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const double &Expected, const double &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { int Arg0 = 4; int Arr1[] = {100}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); double Arg2 = 4.0; verify_case(0, Arg2, getExpected(Arg0, Arg1)); }
	void test_case_1() { int Arg0 = 4; int Arr1[] = {0,100}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); double Arg2 = 3.3333333333333335; verify_case(1, Arg2, getExpected(Arg0, Arg1)); }
	void test_case_2() { int Arg0 = 5; int Arr1[] = {0,0,0,0,0,50,50}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); double Arg2 = 0.0; verify_case(2, Arg2, getExpected(Arg0, Arg1)); }
	void test_case_3() { int Arg0 = 12; int Arr1[] = {9,9,9,9,9,9,9,9,9,9,10}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); double Arg2 = 7.871087929710551; verify_case(3, Arg2, getExpected(Arg0, Arg1)); }

// END CUT HERE

};


// BEGIN CUT HERE 
int main()
{
	system("pause");
    TableSeating ___test; 
    ___test.run_test(-1); 
} 
// END CUT HERE 
    
